package com.fanshuai.algorithms.datastructure.linear;

import com.fanshuai.stack.LinkedStack;
import com.fanshuai.stack.Stack;

import java.util.HashMap;
import java.util.Map;

/**
 * 计算器 支持+, -, *, /, ^, 以及多级括号
 */
public class CalculatorHigh {
    public Stack<Integer> dataStack;
    public Stack<Character> opStack;

    public Map<Character, Integer> opLevel = new HashMap<>();

    public CalculatorHigh() {
        dataStack = new LinkedStack<>();
        opStack = new LinkedStack<>();

        /**
         * 操作符优先级  + - 为1；  * / 为2；  ^ 为3  (为0， )为4
         */
        opLevel.put('(', 0);
        opLevel.put('+', 1);
        opLevel.put('-', 1);
        opLevel.put('*', 2);
        opLevel.put('/', 2);
        opLevel.put('^', 3);
        opLevel.put(')', 4);
    }

    public void clear() {
        dataStack = new LinkedStack<>();
        opStack = new LinkedStack<>();
    }

    private static boolean isDigit(char ch) {
        return ch >= '0' && ch <= '9';
    }

    /**
     * 根据表达式计算值 表达式有数字，+, -, *, /, ^，支持多级括号
     *
     * 首先提取操作数，操作数为连续的数字字符，然后将操作数压入操作数栈
     * 然后根据操作符优先级做响应的操作:
     * （1）运算符栈为空，或者当前操作符优先级大于栈顶操作符优先级，运算符压入运算符栈
     * （2）当前操作符优先级小于等于栈顶操作符优先级，弹出操作数栈顶2个元素，弹出运算符栈顶元素，计算结果，并压入操作数栈
     * （3）继续操作2，知道不满足条件，将当前运算符压入运算符栈
     *
     * 括号处理：括号表达式为递归结构，使用递归求解多级括号表达式
     * @param expression
     * @return
     */
    public static int calc(String expression) {
        SubExpression subExpression = calc0(expression, 0);
        return subExpression.answer;
    }

    static class SubExpression {
        public int answer; //子表达式计算结果
        public int lastIndex; //子表达式在 主表达式中最后一个字符的索引值，即子表达式右括号的索引值

        public SubExpression(int answer, int lastIndex) {
            this.answer = answer;
            this.lastIndex = lastIndex;
        }
    }

    private static SubExpression calc0(String expression, int startIndex) {
        CalculatorHigh calculatorHigh = new CalculatorHigh(); //递归算法，每一层均初始化新的计算器

        boolean digitMode = false;
        int digit = 0;
        for (int i = startIndex; i < expression.length(); i++) {
            char ch = expression.charAt(i);
            if (Character.isWhitespace(ch)) {
                continue;
            }

            if (isDigit(ch)) {
                digitMode = true;
                digit = digit * 10 + (ch - '0');
                if (i == expression.length() - 1) {
                    calculatorHigh.dataStack.push(digit);
                    digit = 0;
                    digitMode = false;
                }
                continue;
            }
            if (digitMode) {
                calculatorHigh.dataStack.push(digit);
                digit = 0;
                digitMode = false;
            }

            if (!calculatorHigh.opLevel.containsKey(ch)) {
                continue;
            }

            if (ch == '(') {
                /**
                 * 左括号为子表达式，进入递归。计算结果后，压入操作数栈，并将i指针移动到子表达式末尾右括号
                 * 进入递归后，会初始化新的计算器。
                 */
                SubExpression subExpression = calc0(expression, i + 1);
                calculatorHigh.dataStack.push(subExpression.answer);

                i = subExpression.lastIndex;
                continue;
            }
            if (ch == ')') {
                /**
                 * 到达右括号时，使用子表达式的计算器计算结果，并将结果和i指针返回
                 */
                while (!calculatorHigh.opStack.isEmpty()) {
                    int v1 = calculatorHigh.dataStack.pop();
                    int v2 = calculatorHigh.dataStack.pop();
                    char op = calculatorHigh.opStack.pop();

                    int v = Calculator.calc0(v2, v1, op);
                    calculatorHigh.dataStack.push(v);
                }

                return new SubExpression(calculatorHigh.dataStack.pop(), i);
            }

            if (calculatorHigh.opStack.isEmpty()) {
                calculatorHigh.opStack.push(ch);
                continue;
            }

            int curOpLevel = calculatorHigh.opLevel.get(ch);
            int topOpLevel = calculatorHigh.opLevel.get(calculatorHigh.opStack.peek());
            if (curOpLevel > topOpLevel) {
                calculatorHigh.opStack.push(ch);
            } else {
                while (!calculatorHigh.opStack.isEmpty() && curOpLevel <= topOpLevel) {
                    int v1 = calculatorHigh.dataStack.pop();
                    int v2 = calculatorHigh.dataStack.pop();
                    char op = calculatorHigh.opStack.pop();

                    int v = Calculator.calc0(v2, v1, op);
                    calculatorHigh.dataStack.push(v);

                    if (!calculatorHigh.opStack.isEmpty()) {
                        topOpLevel = calculatorHigh.opLevel.get(calculatorHigh.opStack.peek());
                    }
                }
                calculatorHigh.opStack.push(ch);
            }
        }

        while (!calculatorHigh.opStack.isEmpty()) {
            int v1 = calculatorHigh.dataStack.pop();
            int v2 = calculatorHigh.dataStack.pop();
            char op = calculatorHigh.opStack.pop();

            int v = Calculator.calc0(v2, v1, op);
            calculatorHigh.dataStack.push(v);
        }

        int answer = calculatorHigh.dataStack.pop();
        return new SubExpression(answer, expression.length());
    }

    public static void main(String[] args) {
        String exp = "1 + 2 + 3";
        String exp2 = "1 + 2 * 3 + 4";
        String exp3 = "23 - 45 + 12 * 4 + 32 - 23 / 2";
        String exp4 = "23 - 45 + 12 * 4 + 32 - 23 / 2 * 2 ^ 3";

        int r1 = 0;
//        r1 = CalculatorHigh.calc(exp);
//        System.out.println(r1);
//
//        r1 = CalculatorHigh.calc(exp2);
//        System.out.println(r1);
//
//        r1 = CalculatorHigh.calc(exp3);
//        System.out.println(r1);
//
//        r1 = CalculatorHigh.calc(exp4);
//        System.out.println(r1);

        String exp5 = "(2 + 3) * 4";
        String exp6 = "(21 + 32 * 10 * (12 * 13)) + 5 / 2 ^ 2";
        String exp7 = "12 + 21 * 2 + (5 / 2 + 11 * (12 - 2) + (2 + 3) * (12 / (1 + (10 / 5))))";

        r1 = CalculatorHigh.calc(exp5);
        System.out.println(r1);

        r1 = CalculatorHigh.calc(exp6);
        System.out.println(r1);

        r1 = CalculatorHigh.calc(exp7);
        System.out.println(r1);
    }

}
